package com.example.algorithms.DynamicProgramming;

/**
 * Created by ZJ on 2020/10/17.
 * 斐波那契数列
 * 1,1,2,3,5,8,13,21,34...
 */
public class FibonacciSequence {

    public static int byRecursion(int n){
        if(n==0||n==1){
            return 1;
        }

        return byRecursion(n-1)+byRecursion(n-2);
    }

    public static int byDynamicProgramming(int n){
        if(n==0||n==1){
            return 1;
        }

        int pre=1;
        int next=1;
        int result=pre+next;
        for(int i=n-2; i>0; i--){
            pre=next;
            next=result;
            result=pre+next;
        }
        return result;
    }

}
